package code201_300.code30_40;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 输入：head = [1,2,2,1]
 * 输出：true
 *
 * 输入：head = [1,2]
 * 输出：false
 *
 */
public class _234isPalindrome {

    /**
     * 思考：有多种方法，题中要求时间O(n),空间(1)。思来想去决定反转链表然后进行判断
     * 注：反转链表只是创建了一个头结点 所以空间还是为1
     *
     * 执行用时：     * 4 ms     * , 在所有 Java 提交中击败了     * 86.63%     * 的用户
     * 内存消耗：     * 48.2 MB     * , 在所有 Java 提交中击败了     * 85.60%     * 的用户
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)return true;
        //寻找初始反转点有多种方法，一种是常规遍历，一种是快慢指针，此处实现快慢指针
        // 快指针一次走两步，慢指针一次走一步。快指针走完，慢指针就到初始节点
        ListNode lower = head;
        ListNode quick = head.next;
        while (quick!=null){
            if(quick.next!=null){
                lower = lower.next;
                quick = quick.next.next;
            }else {
                break;
            }
        }
        //此处lower为初始节点，现在开始反转，抽象成一个方法吧
        lower = reverse(lower.next);
        while (lower!=null){
            if(lower.val == head.val){
                lower = lower.next;
                head = head.next;
            }else {
                return false;
            }
        }
        //注：此处只比较了回文串，正常情况下反转了数组，要将数组反还回去，保证结果不变性
        return true;
    }

    public static ListNode reverse(ListNode head){
        ListNode node = new ListNode();
        while (head!=null){
            ListNode temp = head;
            head = head.next;
            temp.next = node.next;
            node.next = temp;
        }
        return node.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
//        head.next.next = new ListNode(2);
//        head.next.next.next = new ListNode(1);
        System.out.println(isPalindrome(head));
    }

}
